\newcommand{\Amax}{A_{\mbox{\scriptsize max}}}
\newcommand{\Dmax}{D_{\mbox{\scriptsize max}}}
\newcommand{\emax}{e_{\mbox{\scriptsize max}}}
\newcommand{\umax}{U_{\mbox{\scriptsize max}}}

\begin{lemma}
\label{lem:Lipschitz}
Given a $q \times r$ matrix $A$, a $q$-vector $b$ such that $Ax \ge
b$ is feasible, and $p \in {\mathbb R}^r$ and $e \in {\mathbb R}^q$
such that $Ap \ge b - e$, there exists $p'$ satisfying $Ap' \ge b$
such that $\|p - p'\|_\infty$ is at most $\emax (\Amax \Dmax)^q$,
where $\emax = \max_j e_j$, $\Amax$ equals $\max_{ij} |A_{ij}|$ and
$\Dmax$ is the largest determinant, in absolute value, of any
submatrix of the matrix consisting of the columns of $A$ and $b$.
\end{lemma}
\begin{proof}
We find a point $y$ such that $Ay \ge b - Ap$ and $\|y\|_\infty \le
\emax (\Amax \Dmax)^q$.  Setting $p' = p+y$ gives us the desired lemma.  We
first note that $Ay \ge b - Ap$ is feasible since it is satisfied by
the point $x - p$, where $x$ satisfies $Ax \ge b$.  Let $d$ equal $b -
Ap$.  Now our goal is to find a $y$ satisfying $Ay \ge d$.  By our
assumption on $p$, we have $d_i \le \emax$ for all $i$.

Consider the following algorithm for constructing $y$.  Set $y = 0$
and $L$ to be the empty LP.  At the end of $i$ iterations, we will
maintain the invariant that $\|y\|_\infty \le (\Amax\Dmax)^i \emax$.  Find any
  constraint $A_k y \ge d_k$ not in $L$ that is not satisfied.  (If no
  such constraint exists, then we are done.)  Add this constraint to
  $L$.  By the invariant on $|y|$, it follows that $|A_k y|$ is at
  most $\Amax^{i+1}\Dmax^i \emax$.  Since $d_k \le \emax$, it follows
    that $|d_k|$ is at most $\Amax^{i+1}\Dmax^i \emax$.  Since the
      right hand side of every inequality of $L$ is at most this
      number, and the left hand side is a submatrix of $A$, by
      Cramer's rule there exists a vertex of $L$, every coordinate of
      which has magnitude at most $\Amax^{i+1}\Dmax^i\emax$ times the
        largest entry in the determinant of any submatrix of $A$,
        which is at most $\Dmax$.  (Note that $L$ is feasible since
        $Ay \ge d$ is feasible.) This yields the desired invariant
        $\|y\|_\infty \le (\Amax\Dmax)^{(i+1)}\emax$.

The above procedure stops in at most $q$ iterations, and yields a
point $y$ such that $\|y\|_\infty \le \emax(\Amax\Dmax)^{q}$, thus
completing the proof of the lemma.
\end{proof}

\begin{corollary}
\label{cor:Lipschitz}
Let $A$ be a $q \times r$ matrix, $b$ be a $q$-vector, and $p$ be
the lexicographically smallest vector in $Ax \ge b$.  Let $b' \in
{\mathbb R}^q$ be such that $Ax \ge b'$ is feasible.  If $p'$ is the
lexicographically smallest vector in $Ax \ge b'$, then $\|p -
p'\|_\infty$ is at most $\emax(\Amax\Dmax)^{qr + r(r+1)}$, where
$\emax = \max_j |b_j - b'_j|$, $\Amax = \max_{i,j} |A_{ij}|$, and
$\Dmax$ is the largest determinant, in absolute value, of any
submatrix of the matrix consisting of columns from $A$ and $b$.
\end{corollary}
\begin{proof}
Let $L$ denote the LP $Ax \geq b'$.  We apply
Lemma~\ref{lem:Lipschitz} with $(A,p,b,e)$ replaced by $(A,p,b',b-b')$
to obtain a point $p'$ satisfying $L$ such that $|p_1 - p'_1|$ is at
most $\emax(\Amax\Dmax)^{q}$.  We add a constraint $x_1 = p'_1$ to the LP
$L$ and apply Lemma~\ref{lem:Lipschitz} with $(A,p,b,e)$ replaced by
$(\tilde{A},p,\tilde{b},\tilde{e})$, where $\tilde{A}$ is the
constraint matrix of $L$, $\tilde{b}$ is the right-hand side of $L$,
and $\tilde{e}$ is the vector obtained by adding two additional
coordinates to $e$, each with magnitude at most $|p_1 - p'_1|$ (for
the two new inequality constraints resulting from the addition of $x_1
= q_1$).  We obtain a new point $p'$ satisfying $L$ such that $|p_1 -
p'_1|$ and $|p_2 - p'_2|$ are both at most $\emax
(\Amax\Dmax)^{2q+2}$.  Repeating this for all the coordinates yields
the lexicographically smallest vector $p'$ of $Ax \ge b'$ with $\|p -
p'\|_\infty$ at most $\emax(\Amax\Dmax)^{qr + r(r+1)}$.  \junk{ To get
  the claim for the lexicographically optimal best response, we first
  apply the above lemma to show that the first coordinate of f(x') is
  close to p.  (Here we use the fact that p is also lexicographically
  optimal.)  We can add the value of the first coordinate as a
  constraint and then apply the lemma again to argue that the second
  coordinate is close to that of p.  Repeating this would multiply the
  exponent in the distance bound we get from the lemma by n.  }
\end{proof}